package com.leetcode.algorithm.y22.m05;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 322. 零钱兑换 
 * https://leetcode.cn/problems/coin-change/
 * 
 * @author jie.deng
 *
 */
class Question0322Solution01 {
	
	public int coinChange(int[] coins, int amount) {
		int[] minCnts = new int[amount + 1];
		// 默认值-1
		Arrays.fill(minCnts, -1);

		// BFS
		minCnts[0] = 0;
		Queue<Integer> idxQueue = new LinkedList<>();
		idxQueue.add(0);

		while (!idxQueue.isEmpty()) {
			int idx = idxQueue.poll().intValue();
			int minCnt = minCnts[idx];
			for (int coin : coins) {
				int nextIdx = idx + coin;
				if (nextIdx == amount) {
					return minCnt + 1;
				}
				if (nextIdx < amount && minCnts[nextIdx] == -1) {
					minCnts[nextIdx] = minCnt + 1;
					idxQueue.offer(nextIdx);
				}
			}
		}
		return minCnts[amount];
	}
	
}